/*********************************************************************************************************
 *  ------------------------------------------------------------------------------------------------------
 *  file description
 *  ------------------------------------------------------------------------------------------------------
 *         \file  list.c
 *        \brief  This is a general C language linked list module, two-way mode and general data structure
 *       \author  Lamdonn
 *        \email  Lamdonn@163.com
 *      \version  1.1.0
 *      \license  GPL2
 *    \copyright  Copyright (C) 2023 Lamdonn.
 ********************************************************************************************************/
#include "vlib.h"
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define IDENT                           (5)

/* list node type define */
typedef struct NODE
{
    struct NODE *prev;                  /* previous node */
    struct NODE *next;                  /* next node */
    void* data;                         /* address for storing entity data */
} NODE, *node_t;

#define _node(address)                  ((node_t)(address))

/* tool */
#define ABS(x)                          ((x)>0?(x):-(x))
#define MAX(x, y)                       ((x)>(y)?(x):(y))
#define MIN(x, y)                       ((x)<(y)?(x):(y))

/* non-existent position */
#define list_npos                       INT_MAX

static int list_init(list_t list, int dsize)
{
    /* allocate base node space */
    list->parent.base = vlib_malloc(sizeof(NODE));
    if (!list->parent.base) return 0;
    
    /* allocate base data for error */
    _node(list->parent.base)->data = vlib_malloc(dsize);
    if (!_node(list->parent.base)->data)
    {
        vlib_free(list->parent.base);
        return 0;
    }

    _node(list->parent.base)->next = list->parent.base;
    _node(list->parent.base)->prev = list->parent.base;

    list->parent.ident = IDENT;
    list->parent.size = 0;
    list->parent.dsize = dsize;

    return 1;
}

static void list_deinit(list_t list)
{
    int index = 0;
    node_t temp = NULL;
    node_t del = NULL;

    /* loop traversal to delete each node and element */
    temp = list->parent.base;
    for (index = 0; index < list->parent.size + 1; index++)
    {
        del = temp;
        temp = temp->next;

        vlib_free(del->data);
        vlib_free(del);
    }

    list->parent.base = NULL;
    list->parent.size = 0;
    list->parent.dsize = 0;
}

list_t list_create(int dsize)
{
    list_t list = NULL;

    if (dsize <= 0) return NULL;

    /* alloc list */
    list = (list_t)vlib_malloc(sizeof(LIST));
    if (!list) return NULL;

    /* init list */
    if (list_init(list, dsize) == 0)
    {
        vlib_free(list);
        return NULL;
    }

    return list;
}

void list_delete(list_t list)
{
    if (!list) return;

    list_deinit(list);
    vlib_free(list);
}

list_t list_copy(list_t list, int begin, int end)
{
    list_t new = NULL;
    int index = 0;
    node_t source = NULL;

    if (!list) return NULL;

    /* check the correctness of the index */
    if (begin > end || end >= list->parent.size || begin < 0) return NULL;

    /* create a list space */
    new = (list_t)vlib_malloc(sizeof(LIST));
    if (new == NULL) return NULL;

    /* initialize list */
    if (list_init(new, list->parent.dsize) == 0)
    {
        goto FREE_LIST;
    }

    /* traverse the source list and assign it to the new list */
    if (begin < list->parent.size - end) /* copy from head to tail */
    {
        source = list->parent.base;
        for (index = 0; index < list->parent.size; index++)
        {
            source = source->next;

            if (begin <= index && index <= end)
            {
                if (list_push_back(new, source->data) == 0)
                {
                    goto FREE_NODES;
                }
            }
        }
    }
    else /* copy from tail to head */
    {
        source = list->parent.base;
        for (index = list->parent.size - 1; index >= 0; index--)
        {
            source = source->prev;

            if (begin <= index && index <= end)
            {
                if (list_push_front(new, source->data) == 0)
                {
                    goto FREE_NODES;
                }
            }
        }
    }
    
    return new;

FREE_NODES:
    list_deinit(new);
FREE_LIST:
    vlib_free(new);
    return NULL;
}

static node_t list_node_next(node_t base, int offset)
{
    while (base && offset--)
    {
        base = base->next;
    }

    return base;
}

static node_t list_node_prev(node_t base, int offset)
{
    while (base && offset--)
    {
        base = base->prev;
    }

    return base;
}

/** 
 *  \brief get the address of item node from list
 *  \param[in] list: list handler
 *  \param[in] index: the index of list
 *  \return address of list item node
 */
static node_t list_node(list_t list, int index)
{
    int i = 0;
    node_t temp = NULL;

    /* check whether the index exceeds the length of the list */
    if (index >= list->parent.size || index < 0)
    {
        return list->parent.base;
    }

    if (index <= (list->parent.size - 1) / 2) /* find from the head */
    {
        temp = _node(list->parent.base)->next;
        for (i = 0; i < index; i++)
        {
            temp = temp->next;
        }
    }
    else /* find from the tail */
    {
        temp = _node(list->parent.base)->prev;
        for (i = list->parent.size - 1; i > index; i--)
        {
            temp = temp->prev;
        }
    }

    return temp;
}

/** 
 *  \brief get the address of two item node from list
 *  \param[in] list: list handler
 *  \param[in] begin: the index 0 of list
 *  \param[in] end: the index 1 of list
 *  \param[out] begin_node: address 0 of list item node
 *  \param[out] begin_node: address 1 of list item node
 *  \return 1: success or 0: fail
 */
static int list_node_begin_end(list_t list, int begin, int end, node_t *begin_node, node_t *end_node)
{
    node_t t_begin = NULL;
    node_t t_end = NULL;

    /* check the correctness of the index */
    if (begin > end || end >= list->parent.size || begin < 0)
    {
        return 0;
    }

    /* calculate the shortest distance */
    if (list->parent.size - 1 - end < begin)
    {
        t_end = list_node(list, end);
        if (begin < end - begin)
        {
            t_begin = list_node(list, begin);
        }
        else  
        {
            t_begin = list_node_prev(t_end, end - begin);
        }
    }
    else  
    {
        t_begin = list_node(list, begin);
        if (list->parent.size - 1 - end < end - begin)
        {
            t_end = list_node(list, end);
        }
        else  
        {
            t_end = list_node_next(t_begin, end - begin);
        }
    }

    *begin_node = t_begin;
    *end_node = t_end;

    return 1;
}

/** 
 *  \brief insert node to list
 *  \param[in] prev_node: prev node
 *  \param[in] data: address of list item dat
 *  \param[in] dsize: size of list items
 *  \return 1: success or 0: fail
 */
static int node_insert(node_t prev_node, void* data, int dsize)
{
    node_t temp_node = NULL;
    node_t next_node = NULL;

    next_node = prev_node->next;
    if (next_node == NULL)
    {
        return 0;
    }

    /* allocate space and assign values */
    temp_node = (node_t)vlib_malloc(sizeof(NODE));
    if (temp_node == NULL) 
    {
        return 0;
    }
    temp_node->data = vlib_malloc(dsize);
    if (temp_node->data == NULL) 
    {
        vlib_free(temp_node); /* release allocated space */
        return 0;
    }
    if (data != NULL) memcpy(temp_node->data, data, dsize);

    /* link node */
    temp_node->next = next_node;
    next_node->prev = temp_node;

    temp_node->prev = prev_node;
    prev_node->next = temp_node;

    return 1;
}

int list_insert(list_t list, int index, void* data)
{
    node_t next_node = NULL;

    if (!list) return 0;

    /* check whether the index exceeds the length of the list */
    if (index > list->parent.size || index < 0)
    {
        return 0;
    }
    else if (index == list->parent.size)
    {
        next_node = list->parent.base;
    }
    else 
    {
        next_node = list_node(list, index);
        if (next_node == list->parent.base)
        {
            return 0;
        }
    }

    if (node_insert(next_node->prev, data, list->parent.dsize) == 0)
    {
        return 0;
    }

    list->parent.size++;

    return 1;
}

int list_push_front(list_t list, void* data)
{
    return list_insert(list, 0, data);
}

int list_push_back(list_t list, void* data)
{
    return list_insert(list, list->parent.size, data);
}

int list_insert_sort(list_t list, void* data, list_sort_rule_t sort_rule)
{
    char insert_flag = 0;
    char violate_flag = 0;
    node_t t_node = NULL;
    void* prev_data = NULL;
    void* next_data = NULL;

    if (!list) return 0;

    t_node = _node(list->parent.base)->next;
    prev_data = data;
    while (t_node != list->parent.base)
    {
        next_data = t_node->data;

        if (sort_rule(prev_data, next_data) < 0)
        {
            violate_flag = 1;
            break;
        }

        if (insert_flag != 1)
        {
            if (sort_rule(prev_data, data) > 0 || sort_rule(data, next_data) > 0)
            {
                /* find the location */
                if (node_insert(t_node->prev, data, list->parent.dsize) == 0)
                {
                    return 0;
                }
                list->parent.size++;

                insert_flag = 1;
            }
        }

        prev_data = next_data;
        t_node = t_node->next;
    }

    if (insert_flag == 0)
    {
        if (list_push_back(list, data) == 0)
        {
            return 0;
        }
    }

    if (violate_flag == 1)
    {
        list_sort(list, 0, list->parent.size - 1, sort_rule);
    }

    return 1;
}

int list_erase(list_t list, int begin, int end)
{
    node_t begin_node = NULL;
    node_t begin0_node = NULL;
    node_t end_node = NULL;
    node_t end0_node = NULL;
    node_t next_node = NULL;
    node_t cur_node = NULL;

    if (!list) return 0;

    /* check the correctness of the index */
    if (begin > end || end >= list->parent.size || begin < 0)
    {
        return 0;
    }

    /* calculate the shortest distance */
    list_node_begin_end(list, begin, end, &begin_node, &end_node);
    begin0_node = begin_node->prev;
    end0_node = end_node->next;

    cur_node = begin_node;
    while (cur_node != end0_node)
    {
        next_node = cur_node->next;

        vlib_free(cur_node->data);
        vlib_free(cur_node);
        list->parent.size--;

        cur_node = next_node;
    }

    begin0_node->next = end0_node;
    end0_node->prev = begin0_node;

    return 1;
}

int list_pop_front(list_t list)
{
    if (!list) return 0;
    return list_erase(list, 0, 0);
}

int list_pop_back(list_t list)
{
    if (!list) return 0;
    return list_erase(list, list->parent.size - 1, list->parent.size - 1);
}


void list_clear(list_t list)
{
    if (!list) return;
    list_erase(list, 0, list->parent.size - 1);
}

void* list_data(list_t list, int index)
{
    if (!list) return NULL;
    return list_node(list, index)->data;
}

int list_get(list_t list, int index, void* data)
{
    void* ptr = NULL;

    if (!list) return 0;

    if (data == NULL) 
    {
        return 0; 
    }

    ptr = list_data(list, index);
    if (ptr == _node(list->parent.base)->data)
    {
        return 0;
    }

    /* assign values */
    memcpy(data, ptr, list->parent.dsize);

    return 1;
}

int list_alter(list_t list, int index, void* data)
{
    void* ptr = NULL;

    if (!list) return 0;

    if (data == NULL) 
    {
        return 0; 
    }

    ptr = list_data(list, index);
    if (ptr == _node(list->parent.base)->data)
    {
        return 0;
    }

    /* overwrite original data */
    memcpy(ptr, data, list->parent.dsize);

    return 1;
}

/** 
 *  \brief check whether the area are the same
 *  \param[in] ref: reference data address
 *  \param[in] cmp: compare data address
 *  \param[in] dsize: size of data
 *  \return 1-same 0-not same
 */
static int list_cmp_func(void* ref, void* cmp, int dsize)
{
    return memcmp(ref, cmp, dsize)==0?1:0;
}

void* list_find(list_t list, void* data, int direction, int which_one, int *out_index)
{
    return list_find_if(list, data, direction, which_one, out_index, list_cmp_func);
}

void* list_find_if(list_t list, void* data, int direction, int which_one, int *out_index, list_condition_t condition)
{
    return list_find_ex(list, data, 0, list->parent.size-1, direction, which_one, out_index, condition);
}

void* list_find_ex(list_t list, void* data, int begin, int end, int direction, int which_one, int *out_index, list_condition_t condition)
{
    void* ptr_ret = NULL;
    node_t t_node = NULL;
    node_t begin_node = NULL;
    node_t end_node = NULL;
    int i = 0;
    int count = which_one;

    if (!list) return NULL;

    if (data == NULL) 
    {
        return _node(list->parent.base)->data; 
    }

    /* check the correctness of the index */
    if (begin > end || end >= list->parent.size || begin < 0)    
    {
        return _node(list->parent.base)->data;
    }

    /* find node */
    if (list_node_begin_end(list, begin, end, &begin_node, &end_node) == 0)
    {
        return _node(list->parent.base)->data;
    }

    if (direction == LIST_DIR_H2T)
    {
        i = begin;
        t_node = begin_node;
        while (t_node != end_node->next)
        {
            if (condition(data, t_node->data, list->parent.dsize) != 0)
            {
                if (count == 0)
                {
                    ptr_ret = t_node->data;
                    *out_index = i;
                    break;
                }
                count--;
            }

            t_node = t_node->next;
            i++;
        }
    }
    else if (direction == LIST_DIR_T2H)
    {
        i = end;
        t_node = end_node;
        while (t_node != begin_node->prev)
        {
            if (condition(data, t_node->data, list->parent.dsize) != 0)
            {
                if (count == 0)
                {
                    ptr_ret = t_node->data;
                    *out_index = i;
                    break;
                }
                count--;
            }

            t_node = t_node->prev;
            i--;
        }
    }
    else  
    {
        return _node(list->parent.base)->data;
    } 

    return ptr_ret;
}

int list_remove(list_t list, void* data)
{
    return list_remove_if(list, data, list_cmp_func);
}

int list_remove_if(list_t list, void* data, list_condition_t condition)
{
    return list_remove_ex(list, data, 0, list->parent.size-1, LIST_DIR_H2T, 0, condition);
}

int list_remove_ex(list_t list, void* data, int begin, int end, int direction, int count, list_condition_t condition)
{
    node_t temp_node = NULL;
    node_t prev_node = NULL;
    node_t next_node = NULL;
    node_t begin_node = NULL;
    node_t end_node = NULL;
    int max_count = count;
    int ret_count = 0;

    if (!list) return 0;

    if (data == NULL) 
    {
        return 0; 
    }

    /* check the correctness of the index */
    if (begin > end || end >= list->parent.size || begin < 0)    
    {
        return 0;
    }

    /* find node */
    if (list_node_begin_end(list, begin, end, &begin_node, &end_node) == 0)
    {
        return 0;
    }

    if (direction == LIST_DIR_H2T)
    {
        temp_node = begin_node;
        while (temp_node != end_node->next && temp_node != list->parent.base)
        {            
            if (condition(data, temp_node->data, list->parent.dsize) != 0)
            {
                prev_node = temp_node->prev;
                next_node = temp_node->next;

                prev_node->next = next_node;
                next_node->prev = prev_node;

                vlib_free(temp_node->data);
                vlib_free(temp_node);
                list->parent.size--;

                temp_node = prev_node;

                ret_count++;
                if (count != 0)
                {
                    max_count--;
                    if (max_count == 0)
                    {
                        break;
                    }
                }
            }

            temp_node = temp_node->next;
        } 
    }
    else if (direction == LIST_DIR_T2H) 
    {
        temp_node = end_node;
        while (temp_node != begin_node->prev && temp_node != list->parent.base)
        {            
            if (condition(data, temp_node->data, list->parent.dsize) != 0)
            {
                prev_node = temp_node->prev;
                next_node = temp_node->next;

                prev_node->next = next_node;
                next_node->prev = prev_node;

                vlib_free(temp_node->data);
                vlib_free(temp_node);
                list->parent.size--;

                temp_node = next_node;

                ret_count++;
                if (count != 0)
                {
                    max_count--;
                    if (max_count == 0)
                    {
                        break;
                    }
                }
            }

            temp_node = temp_node->prev;
        }
    }
    else 
    {
        return 0;
    }

    return ret_count;
}

/** 
 *  \brief exchange data between two nodes
 *  \param[in] node0: node 0
 *  \param[in] node1: node 1
 *  \return 1: success or 0: fail
 */
static int node_swap_data(node_t node0, node_t node1)
{
    void* temp_data = NULL;

    if (node0 == NULL || node1 == NULL)
    {
        return 0;
    }

    /* swap pointer */
    temp_data = node0->data;
    node0->data = node1->data;
    node1->data = temp_data;

    return 1;
}

int list_switch(list_t list, int index0, int index1)
{
    node_t node0 = NULL;
    node_t node1 = NULL;

    if (!list) return 0;

    /* check the correctness of the index */
    if (index0 >= list->parent.size || index1 >= list->parent.size || index0 < 0 || index1 < 0 || index0 == index1)
    {
        return 0;
    }

    node0 = list_node(list, index0);
    node1 = list_node(list, index1);

    node_swap_data(node0, node1);

    return 1;
}

void list_swap(list_t list, list_t swap)
{
    LIST temp;

    if (!list) return;
    if (!swap) return;

    temp = *list;
    *list = *swap;
    *swap = temp;
}

int list_reverse(list_t list, int begin, int end)
{
    node_t prev_node = NULL;
    node_t next_node = NULL;
    int i = 0;

    if (!list) return 0;

    /* check the correctness of the index */
    if (begin > end || end >= list->parent.size || begin < 0 || begin == end)
    {
        return 0;
    }

    if (list_node_begin_end(list, begin, end, &prev_node, &next_node) == 0)
    {
        return 0;
    }

    i = (end - begin + 1) / 2;
    while (i--)
    {
        node_swap_data(prev_node, next_node);

        prev_node = prev_node->next;
        next_node = next_node->prev;
    }

    return 1;
}

int list_splice(list_t list, int index, list_t list_s, int begin, int end)
{
    node_t op_next = NULL;
    node_t s_cur = NULL;
    node_t prev_node = NULL;
    list_t temp_list = NULL;

    int i = 0;
    int cnt = 0;

    if (!list) return 0;
    if (!list_s) return 0;

    /* check the correctness of the index */
    if (index > list->parent.size || index < 0)
    {
        return 0;
    }
    if (begin > end || end >= list_s->parent.size || begin < 0)
    {
        return 0;
    }

    /* check whether thr two lists are of the same type */
    if (list->parent.dsize != list_s->parent.dsize)
    {
        return 0;
    }

    if (list_s == list && begin <= index && index <= end)
    {
        temp_list = list_copy(list_s, begin, end);
        if (temp_list == NULL)
        {
            return 0;
        }

        s_cur = ((node_t)(temp_list->parent.base))->next;
    }
    else  
    {
        s_cur = list_node(list_s, begin);
    }

    if (index == list->parent.size)
    {
        op_next = _node(list->parent.base);
    }
    else  
    {
        op_next = list_node(list, index);
    }

    /* insert to list */
    cnt = end - begin + 1;
    prev_node = op_next->prev;
    for (i = 0; i < cnt; i++)
    {
        if (node_insert(prev_node, s_cur->data, list->parent.dsize) == 0)
        {
            goto FREE_NODES;
        }
        list->parent.size++;

        /* move to next node */
        s_cur = s_cur->next;
        prev_node = prev_node->next;
    }

    if (temp_list != NULL)
    {
        list_delete(temp_list);
    }

    return 1;

FREE_NODES:
    if (i > 0)
    {
        list_erase(list, index, index + i - 1);
    }
    if (temp_list != NULL)
    {
        list_delete(temp_list);
    }
    return 0;
}

/** 
 *  \brief quick sort algorithm to sort subsequence
 *  \param[in] begin: the begin node of subsequence
 *  \param[in] end: the end node of subsequence
 *  \param[in] b_index: the index of begin node in list
 *  \param[in] e_index: the index of end node in list
 *  \param[in] sort_rule: collation
 *  \return 1: success or 0: fail
 */
static int list_node_quick_sort(node_t begin, node_t end, int b_index, int e_index, list_sort_rule_t sort_rule)
{
    node_t temp_node = begin;
    node_t i_node = begin;
    node_t j_node = end;
    int i = b_index;
    int j = e_index;

    if (b_index >= e_index)
    {
        return 0;
    }

    while (i != j)
    {
        while (sort_rule(j_node->data, temp_node->data) <= 0 && j > i) 
        {
            j_node = j_node->prev;
            j--;
        }
        while (sort_rule(i_node->data, temp_node->data) >= 0 && j > i) 
        {
            i_node = i_node->next;
            i++;
        }

        if (j > i)
        {
            node_swap_data(i_node, j_node);
        }
    }
    node_swap_data(i_node, temp_node);

    list_node_quick_sort(begin, i_node, b_index, i, sort_rule);
    list_node_quick_sort(i_node->next, end, i + 1, e_index, sort_rule);

    return 1;
}

int list_sort(list_t list, int begin, int end, list_sort_rule_t sort_rule)
{
    node_t node_i = NULL;
    node_t node_j = NULL;

    if (!list) return 0;
    if (!sort_rule) return 0;

    /* check the correctness of the index */
    if (begin >= end || end >= list->parent.size || begin < 0)
    {
        return 0;
    }

    if (list_node_begin_end(list, begin, end, &node_i, &node_j) == 0)
    {
        return 0;
    }

    list_node_quick_sort(node_i, node_j, begin, end, sort_rule);

    return 1;
}

int list_size(list_t list)
{
    if (!list) return 0;
    return list->parent.size;
}

int list_empty(list_t list)
{
    if (!list) return 1;
    return list->parent.size==0?1:0;
}

void list_traverse(list_t list, int direction, list_traverse_t traverse)
{
    node_t t_node = NULL;
    int index = 0;

    if (!list) return;
    if (!traverse) return;

    if (direction == LIST_DIR_H2T)
    {
        t_node = _node(list->parent.base)->next;
        index = 0;
        while (t_node != _node(list->parent.base))
        {
            traverse(index, t_node->data);
            t_node = t_node->next;
            index++;
        }
    }
    else if (direction == LIST_DIR_T2H)
    {
        t_node = _node(list->parent.base)->prev;
        index = list->parent.size - 1;
        while (t_node != _node(list->parent.base))
        {
            traverse(index, t_node->data);
            t_node = t_node->prev;
            index--;
        }
    }
}

void* list_error(list_t list)
{
    if (!list) return NULL;
    return _node(list->parent.base)->data;
}

void* list_iterator_begin(vobject_t object)
{
    if (!object) return NULL;
    return ((node_t)(((list_t)object)->parent.base))->next;
}

void* list_iterator_end(vobject_t object)
{
    if (!object) return NULL;
    return ((node_t)(((list_t)object)->parent.base))->prev;
}

void* list_iterator_move(vobject_t object, void *node, int step)
{
    node_t n = node;
    if (step > 0)
    {
        while (step--) n = n->next;
    }
    else if (step < 0) 
    {
        while (step++) n = n->prev;
    }
    return (void *)n;
}

void list_iterator_nfs(void *node, void **first, void **second)
{
    if (!node) return;
    if (first) *first = NULL;
    if (second) *second = ((node_t)node)->data;
}

void list_algorithm_swap(vobject_t object, void *node0, void *node1)
{
    list_t list = (list_t)object;
    node_t n0 = node0, n1 = node1;
    void *temp;
    temp = n0->data;
    n0->data = n1->data;
    n1->data = temp;
}
